\chapter{在量子计算理论的发展中，哪些人做出过特别杰出的贡献？}

Climber.pI
Climber.pI​​​知乎知识会员
计算机科学话题下的优秀答主
编辑推荐
366 人赞同了该回答
最近正好在写综述, 就说一些大概知道人家在干啥的工作. 这里主要讨论量子计算复杂性相关的工作, 简单涉及一些基于量子计算的程序语言与体系结构的工作. 不涉及量子通信与纠错编码, 以及量子信息实验方面的工作.

理解下面的内容, 可能会需要一些可计算性以及计算复杂性的背景.

1. 量子计算复杂性与计算模型

类似经典的可计算性理论, 首先被讨论的是图灵机和线路模型. 1985年, Oxford 的 David Deutsch 第一次给出了量子图灵机的定义[1], 不过这个定义被认为不太好. 1993年, Andrew Yao 证明量子图灵机和量子线路模型等价[2], 不过这篇工作并不在他之后图灵奖给出的文献列表中.

之后对应于经典计算复杂性理论, 首先应该讨论 P 类和 NP 类的类似物. 1997年, UC Berkeley 的 Umesh Vazirani 提出了 BQP 类[4]. (大致相当于确定性图灵机的 P 类, 不过是不是这里最早提出的不确定) 所谓量子计算机对于某些问题的指数级加速, 大概就是这些问题属于 NP 类和 BQP 类, 但是不属于 P 类. Vazirani 老爷子在 edX 上开了门量子计算的介绍性课程. 而 NP 类的量子计算版本是 QMA 类, 由 Caltech 的 Alexei Kitaev 在1999年提出 [6]. (大致相当于确定性图灵机的 NP 类) 他的 Classical and Quantum Computation 一书中也给了介绍, 不过里面叫 BQNP. 到了 2006年, Alexei Kitaev 等人找到了 QMA-Complete 问题[11]: k-Local Hamilton Problem.

还有一些关于量子计算复杂性的工作. 2005年, MIT 的 Scott Aaronson 提出了 PostBQP 类[10], 并证明了它和概率图灵机的 PP 类等价. 2010年, Waterloo 的 John Watrous 等人(JJUW, 第二个是季铮锋)证明了 QIP类(量子交互式证明系统)与 PSPACE 类(多项式空间)等价[13]. 在经典的计算复杂性理论中, 我们知道 IP类(交互式证明系统) 和 PSPACE 类等价, 并且可以得到 PH 类(多项式层次)的包含关系.

然后还有两种没有经典对应的计算模型笔者稍有些了解. 一是拓扑量子计算, 由 Caltech 的 Alexei Kitaev 在1997 年最早提出, 并指出拓扑量子计算可以从硬件层面上容错. 不过拓扑量子计算目前并没有合适的物理实现, Majorana 费米子仅能实现部分量子门. 印象中 Microsoft Research 的 Station Q 在花很大力气搞. 此外 Alexei Kitaev 提出的 Solovay-Kitaev Theorem 给出了在一定错误率下, 多项式规模构造量子线路的方法, Github 上大概有好几个用这东西写编译器的项目.

二是绝热量子计算, 这个和今年比较出名的 DWave 颇有些关系. 早在 2000年, Michael Sipser 等人提出了绝热量子计算模型[7], 嗯 Sipser 就是某本计算理论教材的作者. 2008年, Dorit Aharonov 等人证明了绝热量子计算模型和量子线路模型等价[12], 这一工作最早发布在 FOCS 2004, 后来投了 SIAM Computing. 也就是说 DWave 大概有可能变成通用量子计算机.

2. 量子算法

对外界影响比较大的有两个, 相对于经典算法都是指数级加速.

一是 Shor 算法(基于 Quantum fourier transform).

1994年, MIT 的 Peter Shor 提出了第一个实用的量子算法(Shor 算法)[3](文章发在 FOCS 上), 也几乎是目前最为广为人知的量子算法, 指出了RSA 被破解的潜在可能性. 但是其实 Shor 算法还是很暴力的所以嘛... BTW, Peter Shor 凭借这一工作拿到了 1999 年的 Gödel Prize. 印象中 2000 年 Issca Chuang(Quantum Computation and Quantum Information 一书第二作者) 做了个基于 NMR 的 demo.

二是 Quantum Machine Learning 相关的算法(基于 HHL 算法[178]).

在 2013年, MIT 和 Google 的 Seth Lloyd 等人提出了Quantum SVM[14] 和 Quantum PCA[15], 指出了量子计算对这些机器学习算法有指数级加速. 根据 Scott Aaronson 的综述[16], 可以追溯到 2009 年 HHL 算法[18]解线性方程组. 我猜测这可能是 Google 把 UC Santa Barbaba 的 Martinis 组挖过去造量子计算机的原因之一.

除此之外, 还有1996年 Grover 提出的 Grover 搜索算法, 以及 2003年 Andrew Childs 提出的 Quantum Random Walk, 这两个应该都是多项式级加速. 现在的量子算法基本上都是基于上面四类算法, 其实还应该加上 Feynman 提的模拟实际物理系统.

3. 量子程序语言

不得不提的人是 Peter Selinger. 一是因为他发起了 Quantum Physics and Logics, 量子计算比较著名的会议之一; 二是他在一篇QPL 的综述中提出了"quantum data, classical control", 现在的绝大多数 QPL 都是基于这样的思想, 用经典控制流处理量子数据(大概就是布线). 当然也有量子控制流相关的工作.

先说基于经典控制流的, 类似经典计算机的程序语言. Imperative Programming 方面, 比较著名的是 Bernhard Omer 于2003年 提出的 QCL(至今仍在维护). 还有去年 Princeton 的Ali Javadi Abhari和 UCSB 的 Frederic T. Chong 等人提 出的ScaffCC[19]. Functional Programming 方面, Peter Selinger 最早于2004年提出了 QPL[20]. 近年来出现的则是 Green Altenkirch 等人与2013年设计的 Quipper[21], 它是以 Haskell 作为宿主语言的强类型函数式编程语言.

而关于量子控制流, 不得不提的是 Mingsheng Ying. 一是因为 Ying 是中国大陆量子计算领域内最优秀的学者之一, 二是 Ying 在 QPL 领域也是国际上一流学者(QPL 委员会成员). 今年 UTS 等校举办了 Quantum Information Processing(应该算量子信息理论方面的顶会吧?) 应该与他不无关系.

Ying 近年的工作转向了基于量子控制流的量子计算程序语言, 包括量子程序的 Floyd-Hoare Logic[17] 以及一系列量子控制流(如循环, 递归)相关的工作. Youtube 上有个 Talk 介绍了 Ying 去年利用二次量子化讨论程序叠加态的工作[22]. 而他在 2000 年提出了基于 Neumann的量子逻辑(orthomodular lattice)上的自动机理论[8][9], 是Yao 回国之前中国大陆关于量子计算最好的工作. 前文中 QIP = PSPACE 一文中第二作者 Zhengfeng Ji 便是 Ying 的学生.

4. 量子计算机体系结构

最早的编译过程的讨论似乎是由 Columbia 的 Krysta Svore 和 Alfred Aho 等人在 2006 年给出[23].

这里的 Alfred Aho 就是龙书的第一作者, 他的个人主页上有几个关于量子计算在 CS 方面工作综述的 Slides, 非常值得一看. 而 Krysta Svore 是 Microsoft Research QuArC Group 目前的负责人.

另外有些类似 FPGA 的系统设计. 如2009 年, UMich 的 Viamontes, Markov 和 Hayes 实现了量子线路 模拟系统 QuIDDPro[36]. 以及 Microsoft Research Station Q的Dave Wecker和Krysta M. Svore设计的 LIQUi>, 它以 F#作为宿主语言, 能够嵌入式的编译和模拟量子算法和线路, 并对布线进行了优化.

除此之外, 还有些实验相关的工作, 完全不熟悉就不乱说了.

Reference

[1] Deutsch, David (July 1985).

"Quantum theory, the Church-Turing principle and the universal quantum computer"
. Proceedings of the Royal Society A400 (1818): pp. 97–117.

[2]

Andrew Yao
(1993). Quantum circuit complexity. 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.

[3] Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput.26 (5): 1484–1509,

arXiv
:

quant-ph/9508027v2
,

Bibcode
:

1999SIAMR..41..303S
,

doi
:

10.1137/S0036144598347011
.

[4] Bernstein and Vazirani, Quantum complexity theory,

SIAM Journal on Computing
, 26(5):1411-1473, 1997.

[5] Kitaev, A. Yu.. "Fault-tolerant quantum computation by

anyons
.".

arXiv
:

quant-ph/9707021v1
[6] Dorit Aharonov; Tomer Naveh (2002). "Quantum NP - A Survey".

arXiv
:

quant-ph/0210077v1
[7] E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution, arXiv:quant-ph/0001106.

[8] Ying M. Automata theory based on quantum logic.(I)[J]. International Journal of Theoretical Physics, 2000, 39(4): 985-995.

[9] M.S. Ying, A theory of computation based on quantum logic, Theoretical Computer Science 344 (2005) 134–207.

[10] Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A461 (2063): 3473–3482.

Bibcode
:

2005RSPSA.461.3473A
.

doi
:

10.1098/rspa.2005.1546
[11] Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). "The Complexity of the Local Hamiltonian Problem". SIAM Journal on Computing(Philadelphia:

Society for Industrial and Applied Mathematics
) 35 (5): 1070–1097.

arXiv
:

quant-ph/0406180v2
[12] Aharonov D, Van Dam W, Kempe J, et al. Adiabatic quantum computation is equivalent to standard quantum computation[J]. SIAM review, 2008, 50(4): 755-787.

[13] Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya;

Watrous, John
(2010). "QIP = PSPACE". STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing. ACM. pp. 573–582.

ISBN978-1-4503-0050-6
.

[14] Rebentrost P, Mohseni M, Lloyd S. Quantum support vector machine for big data classification[J]. Physical review letters, 2014, 113(13): 130503.

[15] Lloyd S, Mohseni M, Rebentrost P. Quantum principal component analysis[J]. Nature Physics, 2014, 10(9): 631-633.

[16] Aaronson S. Read the fine print[J]. Nature Physics, 2015, 11(4): 291-293.

[17] Ying M. Floyd--hoare logic for quantum programs[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 2011, 33(6): 19.

[18] Aram W. Harrow, Avinatan Hassidim and Seth Lloyd (2009) Quantum Algorithm for Linear Systems of Equations, Physical Review Letters 103 150502

[19] JavadiAbhari A, Patil S, Kudrow D, et al. ScaffCC: a framework for compilation and analysis of quantum computing programs[C]//Proceedings of the 11th ACM Conference on Computing Frontiers. ACM, 2014: 1.

[20] Selinger P. Towards a quantum programming language[J]. Mathematical Structures in Computer Science, 2004, 14(04): 527-586.

[21] Green A S, Lumsdaine P L F, Ross N J, et al. Quipper: a scalable quantum programming language[C]//ACM SIGPLAN Notices. ACM, 2013, 48(6): 333-342.

[22] Ying M, Yu N, Feng Y. Alternation in quantum programming: from superposition of data to superposition of programs[J]. arXiv preprint arXiv:1402.5172, 2014.

[23] Svore K M, Aho A V, Cross A W, et al. A layered software architecture for quantum computing design tools[J]. Computer, 2006 (1): 74-83.

[24] Viamontes G F, Markov I L, Hayes J P. Quantum circuit simulation[M]. Springer Science & Business Media, 2009.